1. Field
The present invention pertains to a method and apparatus for implementing a binary search algorithm. More particularly, the present invention pertains to using exclusively combinatorial logic elements to implement a next address determination within a binary search algorithm.
2. Background Information
Binary search algorithms are used to locate a particular entry (known as the "compared") within a sorted array of elements. The elements of a sorted array may be visualized as a series of vertically stacked shelves. In a 16 element array, for example, the top shelf corresponds to element 1 and the bottom shelf corresponds to element 16. The numbers or words stored within the 16 elements of the array are typically sorted in increasing order from element 1 to element 16. Each array element is identified with a unique address.
A typical binary search algorithm includes a comparator and a next address generator. A binary search algorithm usually begins conducting a search at the middle array element. The comparator compares the compared to the entry stored in the middle array element and sends a comparison result to the next address generator. The next address logic circuit receives the comparison result from the comparator and uses this result to determine the address of the next array element which should be searched.
Current next address generators typically determine the next address using two pointers. At the beginning of a search, one pointer is positioned at the address of the top element of the array and the second pointer is positioned at the address of the bottom element of the array. The number of array addresses between the pointers is then determined and divided in half (averaged) to identify the address of the middle array element. One of the two pointers is then positioned at the middle array element. The comparator then compares the compared with the value stored in the middle array element and sends a comparison result to the next address generator. The next address generator uses the comparison result and the previous address to determine the next address which will be searched. If the compared is greater than the value stored in the middle element, the lower half of the array will be searched using the averaging technique described above and the upper half of the array will be eliminated from consideration. If the compared is not greater than the value stored in the middle element, the upper half of the array will be searched using the averaging technique and the lower half of the array will be eliminated from consideration. These comparing and eliminating steps are repeated until the comparand is located within an array element or until all the array elements have been searched.
A circuit used to determine the next address using the pointer method described above employs some form of memory to maintain the pointer positions. Typically, the circuit comprises a combination of devices which implement both combinatorial logic and sequential logic. Generally, combinatorial logic includes operations which are executed using boolean algebra. Boolean algebra is two-state (binary) symbolic logic used in digital systems. The two binary states are typically a "1" and a "0". Thus boolean algebra entails performing operations on binary words which consist of 1's and 0's. The circuit components which perform boolean algebra operations are known as logic gates. AND, OR and NOT logic gates perform the three basic boolean algebra operations. These three gates may be combined to perform more complex operations. Combinatorial logic gates receive binary words at one or more inputs, perform an operation on the input binary word(s), and output a binary word(s) which represent the result of the performed operation. Sequential logic is similar to combinatorial logic. However, devices which perform sequential logic include a capacity to store binary data for a period of time. Thus, the binary word(s) input to a sequential logic device or the binary result of the sequential logic operation may be stored in a memory. Flip flops and shift registers are examples of sequential logic devices. Flip flops and/or shift registers are typically included within a circuit which implements the pointer method described above to maintain the pointer positions.
The time required for a binary search algorithm to search an array may be reduced by either reducing the number of logic gates between the input and output of the next address circuit or by reducing the number of logic gates between the input and output of the comparator. In general, circuits which consist purely of combinatorial logic elements are more simple than circuits which include sequential logic elements. Accordingly, there is a need for a search procedure which is purely combinatorial and includes a minimal number of logic gates between the input and output of the next address generator.